1. Field of the Invention
The present invention relates to a Viterbi decoder decoding data using a trellis diagram, and more particularly, to a Viterbi decoder capable of improving a data decoding speed without being limited by a sampling speed of a sampling and holding circuit.
2. Description of the Related Art
With the development of communication technology, wireless mobile communication technology has been popularized throughout the world. Since data is wirelessly transmitted and received in the wireless mobile communication environment, a receiver cannot precisely receive data from a transmitter. In other words, data may be distorted during the transmission of the data due to noise or like.
In general, the transmitter codes and transmits data to be transmitted, and the receiver decodes the coded data so as to reduce the possibility of the data being distorted. Also, coding and decoding operations are performed in a process of storing data in a recording medium such as a digital versatile disk (DVD).
Examples of such a coding method include a block coding method, a convolution coding method, and the like. In the block coding method, an input data bit including additional data having a predetermined bit size is coded. In the convolution coding method, previously input data is stored in a memory so as to be coded based on a relationship between a current input value and a previous input value. The convolution coding method has higher error correction efficiency than the block coding method and thus is generally used.
A Viterbi decoder decodes data coded using the convolution coding method. Such a Viterbi decoder performs a several-step operation to determine an optimum path from accumulated result values so as to correct an error.
FIG. 1 is a view illustrating a trellis diagram used in a general Viterbi decoder. In the trellis diagram shown in FIG. 1, a constraint length is 3, and a coding rate is ½. Since the constraint length is 3, a previous input value may be 00, 10, 01, and 11. The Viterbi decoder back-tracks an optimum path in which an accumulated distance value is minimum after a predetermined period of time using a difference between a peculiar code allotted to each branch on the trellis diagram and a input signal as a metric. In detail, if the optimum path passes branches marked with solid lines, the Viterbi decoder decodes the input signal as 0. If the optimum path passes branches marked with dotted lines, the Viterbi decoder decodes the input signal as 1. Thus, if the input signal is different from a substantially transmitted signal, an error can be corrected.
Nodes a, b, c, and d on the trellis diagram compute the shortest distance reaching a destination using Equation 1:Di,j=min{Dk,l+dij,kl, (k,l)εS(i,j)}  (1)wherein Dk,l denotes the shortest distance from a (k,l)th cell to a destination, dij,kl denotes a partial distance from a (i,j)th cell to a(k,l)th cell, S(ij) denotes a set of cells around the (i,j)th cell, and min denotes a function outputting a minimum value of enumerated items.
The conventional Viterbi decoder does not realize all nodes on the trellis diagram as hardware but realizes only nodes in a column as hardware. Thus, these nodes performs the operation shown in Equation 1 above with time, i.e., adds a distance value of each branch to accumulated distance values transmitted from previous nodes, and selects a minimum value from the addition results so as to store the selection result in a memory. As a result, if an operation is performed up to a last destination, the conventional Viterbi decoder searches for an optimum path using data stored in the memory. Accordingly, the conventional Viterbi decoder requires additional hardware such as a memory. Also, a back-tracking process must be performed to compute the optimum path in the memory. Thus, decoding time is increased.
To solve these problems, a circular Viterbi decoder disposing cells in positions corresponding to nodes of a trellis diagram and connecting cells corresponding to last processing nodes to cells corresponding to first processing nodes has been developed as disclosed in Korea Registration No. 10-0412934. A conventional circular Viterbi decoder will now be schematically described with reference to FIG. 2. The conventional circular Viterbi decoder includes a decoder 10, an analog data storage 20, a first switch 30, a controller 40, and a sampling and holding unit 50.
The decoder 10 includes a plurality of processing nodes including a plurality of cells vertically disposed to correspond to nodes on a trellis diagram and decodes analog input data using an analog signal processing cell having a circular connection structure in which a last processing node of the plurality of processing nodes is connected to a first processing node.
The analog data storage 20 includes a plurality of condensers, stores analog data input through the sampling and holding unit 50, and transmits the data to the decoder 10 under the control of the controller 40.
The controller 40 controls the first switch 30 according to a predetermined clock signal CLK input from an external source to stores an analog input signal sampled and held by the sampling and holding unit 50 in the analog data storage 20.
The sampling and holding unit 50 samples and holds the analog input signal according to a clock signal CLK having the clock frequency as the clock signal CLK input to the controller 40.
The conventional circular Viterbi decoder does not need to store an output value of each cell doe in an additional memory and thus does not need to include additional hardware. Also, the conventional circular Viterbi decoder applies a predetermined trigger signal to each cell, senses a variation in a lastly output pulse, and performs decoding. Thus, the conventional circular Viterbi decoder does not require a back-tracking process. As a result, decoding time is reduced.
However, since the conventional circular Viterbi decoder adopts one sampling and holding circuit, the conventional Viterbi decoder cannot operate at a speed higher than a sampling speed at which the one sampling and holding circuit can precisely sample and hold an analog input signal. In other words, a decoding speed of the conventional circular Viterbi decoder is limited by the sampling speed of the sampling and holding circuit.